package com.leetcode.array;

/**
 * @author XW
 * @data 2023/11/23 16:35
 * @description最长公共前缀
 */
public class Code14_LongCommonPrefix {
    public static void main(String[] args) {
//        System.out.println("asdf".substring(0,4));
        String[] s = new String[]{"asd","asdf","asdfe"};
        String s1 = new Code14_LongCommonPrefix().longestCommonPrefix1(s);
        System.out.println(s1);
    }


    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 1){
            return strs[0];
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;

    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }




    /**
     * 递归暴力
     * @param strs
     * @return
     */
    public String longestCommonPrefix1(String[] strs) {
        if(strs.length == 1){
            return strs[0];
        }
        String target = "";
        int i = 1;
        target = getLongCommon(strs,target,i);
        return target;

    }

    private String  getLongCommon(String[] strs,String target,int i){
        String str = strs[0];
        if(i > str.length()){
            return target ;
        }
        String s1 = str.substring(0,i);
        for (int j = 1 ; j< strs.length;j++){
            String str1 = strs[j];
            if(i > str1.length()){
                return target;
            }
            String s2 = str1.substring(0,i);
            if(!s2.equals(s1)){
                break;
            }else{
                if(j == strs.length-1){
                    target = s1;
                    i++;
                    target = getLongCommon(strs,target,i);
                }
            }
        }
        return target;

    }
}
